1. Field of the Invention
The present invention relates generally to data compression, and in particular to methods and mechanisms for efficiently compressing and decompressing data in a lossless fashion.
2. Description of the Related Art
Compression techniques are utilized to reduce the amount of data that is transmitted, stored, or otherwise processed. Many of these data compression techniques look at the frequency of occurrence of various values and encode the most frequently used values with a shorter code and encode the infrequently used values with a longer code. Such an approach may be referred to as variable length encoding, and one type of variable length encoding is Huffman encoding. Huffman encoding is a lossless encoding scheme that is utilized in several compression standards (e.g., JPEG). While variable length encoding schemes can be effective, such techniques tend to be computationally costly and inefficient.
For example, Huffman encoding replaces variable-length sequences with shorter variable-length symbols. These shorter variable-length symbols reduce the size of the data, but also cause inefficiencies when performing the encoding and decoding of the data. For example, the decoder does not know the length of each symbol in advance, and so decoding cannot be performed in parallel for multiple symbols. Therefore, there is a need in the art for a faster, more efficient compression and decompression scheme.